package com.atwulidun.recursion;

public class Hanoi {
    private int num;// 用来记录汉诺塔圆盘移动的次数

    // 显示出汉诺塔移动过程的函数
    public void move(int n, String a, String b, String c) {
        if (n == 1) {
            System.out.println(a + "---->" + c);
            num++;
            return;
        }
        // 先把第n个圆盘上的n - 1个圆盘看成一个整体由A移动到B，此时A对应move方法里面的a，B对应move方法里面的c，C对应move方法里面的b
        move(n - 1, a, c, b);// 已经把n-1步调用的过程打印出来了，同时也已经让num++够了圆盘移动的次数，举n=2的例子即可理解
        // 将第n个圆盘由实际的A移动到实际的C
        System.out.println(a + "---->" + c);// 这里只需要打印出单次移动的状况即可
        num++;
        // 再把第n - 1个圆盘看成一个整体由B移动到C，此时B对应move方法里面的a，C对应move方法里面的c，A对应move方法里面的b
        move(n - 1, b, a, c);// 已经把n-1步调用的过程打印出来了同时也已经让num++够了圆盘移动的次数
    }

    // 纯粹求取汉诺塔移动次数的函数
    public static int getMoveNum(int num) {
        if (num == 1) {
            return 1;
        }
        return 2 * getMoveNum(num - 1) + 1;
    }
    public static void main(String[] args) {
//        Hanoi hanoi = new Hanoi();
//        hanoi.move(5, "A", "B", "C");
//        System.out.println(hanoi.num);
        System.out.println(getMoveNum(5));
    }
}
